层次聚类 |
您所在的位置：网站首页 › q learning sarsa › 层次聚类 |
层次聚类
机器学习与数据挖掘
问题
分类
聚类
回归
异常检测
数据清洗
自动机器学习
关联规则
强化学习
结构预测（英语：Structured prediction）
特征工程
特征学习
線上機器學習
無監督學習
半监督学习
排序学习（英语：Learning to rank）
语法归纳（英语：Grammar induction）
監督式學習(分类 · 回归)
决策树
集成（装袋，提升，随机森林）
k-NN
线性回归
朴素贝叶斯
神经网络
逻辑回归
感知器
支持向量机（SVM）
相关向量机（RVM）
聚类
BIRCH
层次
k-平均
期望最大化（EM）
DBSCAN
OPTICS
均值飘移（英语：Mean shift）
降维
因素分析
CCA
ICA
LDA
NMF（英语：Non-negative matrix factorization）
PCA
LASSO
t-SNE（英语：t-distributed stochastic neighbor embedding）
结构预测（英语：Structured prediction）
概率图模型（贝叶斯网络，CRF, HMM）
异常检测
k-NN
局部离群因子（英语：Local outlier factor）
神经网络
自编码
深度学习
多层感知机
RNN
受限玻尔兹曼机
SOM
CNN
Transformer模型
强化学习
Q学习
SARSA
时序差分学习
深度强化学习
理论
偏差/方差困境（英语：Bias–variance tradeoff）
计算学习理论（英语：Computational learning theory）
经验风险最小化
PAC学习（英语：Probably approximately correct learning）
统计学习
VC理论
研讨会
NeurIPS
ICML（英语：International_Conference_on_Machine_Learning）
ICLR
查论编
在数据挖掘和统计学中，层次聚类（英語：Hierarchical clustering）是一种旨在建立聚类的层次结构的聚类分析方法。层次聚类的策略通常有两种： 凝聚（Agglomerative clustering）：一种自底向上方法，从小集群开始，逐渐将其合并，形成更大的集群； 分裂（Divisive clustering）：一种自顶向下方法，从单个集群开始，递归地将其拆分成更小的集群。凝聚和分离的操作通常用贪心算法实现，结果通常用树状图展示。[1] 标准的凝聚层次聚类（Hierarchical agglomerative clustering，HAC）算法的时间复杂度为 O ( n 3 ) {\displaystyle {\mathcal {O}}(n^{3})} ，空间复杂度为 Ω ( n 2 ) {\displaystyle \Omega (n^{2})} ，这使它甚至难以应用于中等规模的数据集中。对于一些特殊情况，效率最优的算法（复杂度为 O ( n 2 ) {\displaystyle {\mathcal {O}}(n^{2})} ）包括SLINK（用于单连接聚类，Single-linkage clustering）[2]和CLINK（用于全连接聚类，Complete-linkage clustering）[3]。当使用堆（Heap）时，一般情况下的时间复杂度降至 O ( n 2 log n ) {\displaystyle {\mathcal {O}}(n^{2}\log n)} ，该改进以更多的内存需求为代价。这种改进方法的内存开销很多时候大到难以实际使用。 除了单连接聚类的特殊情况，除了穷举算法（复杂度 O ( 2 n ) {\displaystyle {\mathcal {O}}(2^{n})} ）外，没有算法可以保证找到最优解。 使用穷举算法的分裂方法的复杂度为 O ( 2 n ) {\displaystyle {\mathcal {O}}(2^{n})} ，不过可以通过更快的启发式方法（例如k-均值算法）进行分裂。 层次聚类的优点是可以采用任何有效的距离测量。当给定距离矩阵时，观测本身是没有必要的。 目录 1 聚集层次聚类 2 分裂层次聚类 3 软件 3.1 开源软件 3.2 商业软件 4 参考文献 聚集层次聚类[编辑] 原始数据
本节将对上图所示的原始数据进行聚集层次聚类（Agglomerative clustering），采取欧几里得距离度量距离。 下图展示了聚类结果的树状图：  聚类结果
在给定高度切割树，会得到一个特定精度的聚类结果。例如，在从上往下数的第二行切割会得到四个集群：{a}、{b, c}、{d, e}和{f}；在第三行切割会得到{a}、{b, c}、{d, e, f}，相比之前，这是一个更粗糙（coarser）的聚类结果，集群的数量更少但集群更大。 该方法合并单独的元素形成集群并得到层次（Hierarchy）。本例有六个元素（{a}、{b}、{c}、{d}、{e} 、{f}），第一步确定哪些元素合并到一个集群，判定标准通常是元素间的距离，选取两个最近的形成集群。 也可以在该步构建距离矩阵（矩阵的第i行第j列的数值为i-j元素之间的距离）。在聚类过程中，行、列被合并并形成新的距离。该方法为实现聚集层次聚类的通用方法，同时对缓存集群之间的距离有益。单连接聚类（英语：Single-linkage_clustering）是一个简单的聚集层次聚类方法。 在完成对距离最短元素b和c的合并后，形成的集群为：{a}、{b, c}、{d}、{e} 、{f}，对其进行进一步的合并需要度量集群{a}和{b, c}之间的距离（即两个集群间的距离）。通常将集群 A {\displaystyle {\mathcal {A}}} 和 B {\displaystyle {\mathcal {B}}} 之间的距离定义为： 两个集群的元素间的最大距离（又称全连接聚类（英语：Complete-linkage_clustering））： max { d ( x , y ) : x ∈ A , y ∈ B } . {\displaystyle \max\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.} 两个集群的元素间的最小距离（又称单连接聚类（英语：Single-linkage_clustering））： min { d ( x , y ) : x ∈ A , y ∈ B } . {\displaystyle \min\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.} 两个集群的元素间的平均距离（又称平均连接聚类（Average linkage clustering），在UPGMA方法中有应用）： 1 | A | ⋅ | B | ∑ x ∈ A ∑ y ∈ B d ( x , y ) . {\displaystyle {1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y).} 所有聚类内方差的总和 被合并的集群方差的增加量 （Ward法（英语：Ward%27s_method）[4]） 候选聚类从同一分布函数生成的概率（V-linkage）当若干对组合具有同样的距离且为最小时，可以随机选取一对形成集群（生成不同的树状图）；也可以同时形成不同的集群（生成唯一的树状图）。[5] 聚类算法的停止准则可以取决于数量（当形成足够少的集群时停止）；也可以取决于距离（当两个集群之间的距离足够远，以至于不能形成新集群时停止）。 分裂层次聚类[编辑]DIANA（DIvisive ANAlysis Clustering）是分裂层次聚类的基础算法。[6] 首先，所有元素归属同一个集群，然后分裂集群，直到所有元素都独立成群。由于存在 O ( 2 n ) {\displaystyle O(2^{n})} 种方法进行分裂，因此需要启发式（Heuristics）算法实现。DIANA选择平均异同度（Average dissimilarity）最大的元素，然后将所有与新集群相似度高于其余集群的元素划分到该集群。 软件[编辑] 开源软件[编辑] ALGLIB用C++和C#实现了多种层次聚类算法 ELKI实现了多种层次聚类算法 Julia在Clustering.jl包中实现了层次聚类[7] Octave（GNU对MATLAB的兼容实现）实现了层次聚类（函数linkage） Orange（一个数据挖掘软件套件）实现了带有交互式树状图可视层次聚类 R有内置的函数和包[8]，提供层次聚类的函数 SciPy在Python中实现了层次聚类 Scikit-learn也在Python中实现了层次聚类 Weka实现了层次聚类 商业软件[编辑] MATLAB中有层次聚类分析 SAS在PROC CLUSTER中包含层次聚类分析 Mathematica有一个层次聚类包 NCSS中实现了层次聚类分析 SPSS中包括层次聚类分析 Qlucore Omics Explorer中包括分层聚类分析 Stata中包括层次聚类分析 CrimeStat中实现了近邻层次聚类算法 参考文献[编辑] ^ Nielsen, Frank. 8. Hierarchical Clustering. Introduction to HPC with MPI for Data Science. Springer. 2016: 195–211 [2023-03-05]. ISBN 978-3-319-21903-5. （原始内容存档于2021-04-17）. ^ R. Sibson. SLINK: an optimally efficient algorithm for the single-link cluster method (PDF). The Computer Journal (British Computer Society). 1973, 16 (1): 30–34 [2023-03-05]. doi:10.1093/comjnl/16.1.30 . （原始内容存档 (PDF)于2014-09-24）.
^ D. Defays. An efficient algorithm for a complete-link method. The Computer Journal (British Computer Society). 1977, 20 (4): 364–6. doi:10.1093/comjnl/20.4.364 .
^ Ward, Joe H. Hierarchical Grouping to Optimize an Objective Function. Journal of the American Statistical Association. 1963, 58 (301): 236–244. JSTOR 2282967. MR 0148188. doi:10.2307/2282967.
^ Fernández, Alberto; Gómez, Sergio. Solving Non-uniqueness in Agglomerative Hierarchical Clustering Using Multidendrograms. Journal of Classification. 2008, 25 (1): 43–65. S2CID 434036. arXiv:cs/0608049 . doi:10.1007/s00357-008-9004-x.
^ Kaufman, L.; Rousseeuw, P.J. 6. Divisive Analysis (Program DIANA). Finding Groups in Data: An Introduction to Cluster Analysis. Wiley. 2009: 253–279 [1990] [2023-03-06]. ISBN 978-0-470-31748-8. （原始内容存档于2023-03-06）.
^ Hierarchical Clustering · Clustering.jl. juliastats.org. [2022-02-28]. （原始内容存档于2023-03-05） （英语）.
^ hclust function - RDocumentation. www.rdocumentation.org. [2022-06-07]. （原始内容存档于2023-03-15） （英语）.
|
，空间复杂度为
Ω
(
n
2
)
{\displaystyle \Omega (n^{2})}
，这使它甚至难以应用于中等规模的数据集中。对于一些特殊情况，效率最优的算法（复杂度为
O
(
n
2
)
{\displaystyle {\mathcal {O}}(n^{2})}
）包括SLINK（用于单连接聚类，Single-linkage clustering）[2]和CLINK（用于全连接聚类，Complete-linkage clustering）[3]。当使用堆（Heap）时，一般情况下的时间复杂度降至
O
(
n
2
log
n
)
{\displaystyle {\mathcal {O}}(n^{2}\log n)}
，该改进以更多的内存需求为代价。这种改进方法的内存开销很多时候大到难以实际使用。
）外，没有算法可以保证找到最优解。
和
B
{\displaystyle {\mathcal {B}}}
之间的距离定义为：
两个集群的元素间的最小距离（又称单连接聚类（英语：Single-linkage_clustering））：
min
{
d
(
x
,
y
)
:
x
∈
A
,
y
∈
B
}
.
{\displaystyle \min\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.}
两个集群的元素间的平均距离（又称平均连接聚类（Average linkage clustering），在UPGMA方法中有应用）：
1
|
A
|
⋅
|
B
|
∑
x
∈
A
∑
y
∈
B
d
(
x
,
y
)
.
{\displaystyle {1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y).}
所有聚类内方差的总和
被合并的集群方差的增加量 （Ward法（英语：Ward%27s_method）[4]）
候选聚类从同一分布函数生成的概率（V-linkage）
种方法进行分裂，因此需要启发式（Heuristics）算法实现。DIANA选择平均异同度（Average dissimilarity）最大的元素，然后将所有与新集群相似度高于其余集群的元素划分到该集群。
【本文地址】